Standford CS140e 流水帐

介绍

CS140e 是今年一月份开的一门使用 Rust 和 Rasberry Pi 教学操作系统的课程，内容包括：

Disks, File systems, I/O, Threads & Processes, Scheduling, Virtual Memory, Protection & Security, Interrupts, Concurrency & Synchronization.

这门课有 5 个 assignment：

我个人蛮喜欢 Rust，再加上下学期上操作系统的课，于是打算在寒假跟着这门课学操作系统。

由于 honor code 的原因，我不会分享实际的代码。

Day 0

Day 0 主要是准备硬件。

官方提供的购物清单如下：

我从淘宝购入硬件，清单如下：

SD 卡和读卡器我都有，就没有再买。除去 RPi 一共 28.88 元，挺便宜的。

过了两日硬件到齐了，做了第一个 assignment 0: blinky。虽然不在同一天，我把它也算进 Day 0 吧。

blinky 主要是让你试一下硬件能不能工作，用 GPIO 去点 LED 灯，写了 loop 让它闪起来，整体来说比较简单。需要注意的是 SD 卡需要的分区得是 bootable 的，文档没提这一点，我当时也忘了，花了不少时间才想起来。

效果可以看我当时发的 tweet。

Day 1

今天做了 assignment 1: shell 五个 phase 里面的三个。

Phase 0 只是些准备工作，不值一提。

Phase 1 是改 25 个 Rust 程序，让它们通过或者不通过编译。主要是熟悉下概念，我之前写过些 Rust，很快就做完了，除了 lifetime 很 ufcs 不太熟悉再学了一遍。

Phase 2 有 4 个 subphas：

后面还有 shell 和 bootloader，明日再战。

Day 2

结果今天只战了 shell（（（（

Phase 3 依然分成几个部分：

今天这个 phase 比之前难做了一些，因为没有提供单元测试了，得自己编译内核拷到 rpi 的 SD 卡上测试。插拔 SD 卡和数据线没法写进 makefile，故而调试起来很麻烦。

时间主要是由于 UART 没实现好用掉的，下次看文档得更认真看。说到文档，BCM2837 的官方文档是有错的，GPIO 部分有个寄存器的值无论高低电位都是 0…… #tuna 上的 @jiegec 告诉我 Standford 提供了订正过的版本。

最后做出来的效果是这样的： cs140e_shell

Day 3

今天做的是实现 bootloader。rpi 利用 XMODEM 协议从 UART 读取内核放到内存中，然后 jump 过去。一共写了 10 行左右，很简单。

然而 debug 花了我一个多小时。从 XMODEM 读内核的过程中如果 timeout 了，会断掉重读。而我初版的程序每次往 rpi 发第二个包时都会收到一个 CANCEL，而且第一个包的 checksum 也会收到一个 NACK。CP2102（用来跟 rpi 做 UART 通讯的 USB 设备）上指示通讯的蓝灯也保持长亮（UART 的接收端会发一个 NAK 请求开始通讯，导致指示灯亮）。到底是什么 bug 导致了这些现象呢？

答案是 timeout 的单位没处理好。原本 UART 驱动里处理 timeout 的代码大概是这样 start + milliseconds_timeout > current_time()。而 current_time 是 rpi 的系统时间，单位是 microsecond，milliseconds_timeout 应该乘上 1000 再做比较。因而 rpi 会因为 timeout 一直给我发 CANCEL，导致内核发不过去。修好了之后 CP2102 的指示灯没再长亮，而是隔大约半秒闪一次（我设的 timeout 是 750ms）。

几经辛苦，assignment 1 总算没有 overdue，赶上了 schedule。目前 assignment 2 还没放出，这篇 blog 估计会鸽两天。

Day 4

话说 Day 3 已经是去年的事情了😂。事实上并不是我弃坑了，而是 Assignment 2 跳票了🌚。原先是 2 月 14 日放出来的，结果到了年三十才放了 phase 1。直到今日（三月三日）都未放出全部内容，甚至测试数据本身有错。但这个课程毕竟第一次出，当下小白鼠也不足为奇。

这个 assignment 主要实现两部分，内存分配器（memory allocator）以及 FAT32 文件系统，我都已经做得七七八八。下面分成两部分讲。

Memory Allocator

首先从 RPi 的固件里读 ATAGS（ARM tags），获取硬件信息。ATAGS 存放在一块连续的内存中，而我们关心的仅仅是其中的内存信息。每个 ATAG 包含三部份，大小，tag，以及数据。ATAG 有多种 varient，其中 tag 决定数据属于何种类型。因此 data 部分使用 union （跟 C 里的 union 类似，属于 untagged union）存放。在 Rust 中，访问 untagged union 与访问 tagged union（即 enum）不同，是 unsafe 的。这部份的工作是封装出一个遍历 ATAGS 返回 tagged union 的 std::Iterator，作为安全的接口供 Allocator 调用。

在 Rust 里，用户可以提供自定义的 allocator 替换掉全局的 allocator，比如将默认的 jemalloc 替换成 glibc 的 malloc。这个特性目前还没 stable，需要 nightly 的编译器，具体可以看（https://github.com/rust-lang/rust/blob/master/src/doc/unstable-book/src/language-features/global-allocator.md）。我实现了基于 Buddy Memory Allocator 的内存分配器，作为 global allocator。在这之后就可以使用堆上的内存，这意味着 std::Vec, std::String, std::HashMap 等等都可以使用了~

File System

目前我实现了一个只读的 FAT32 文件系统以及 ls，cd，cat，pwd 等命令。

首先实现 mbr.rs（Master Boot Record）和 ebpb.rs（Extended Bios Parameter Block）读取诸如 sector 大小，分区大小，每个 cluster 有几个 sector 的信息。基本上只是把数据读到内存再 cast 到相应的 struct 再检查下 magic number 就 ok。

FAT32 文件系统主要由两部分组成，FAT（File Allocation Table）以及 Clusters。实际的文件（或文件夹）数据及元数据存放在 Clusters，以 cluster chain 的形式（chain 不必由连续的 cluster 组成）存在。而 FAT 由若干 FAT entry 组成，每个 FAT entry 长 32 bit，记录一个对应的 cluster 的信息（除了前两个 FAT entry）。FAT entry 的值只有 28 位有意义，根据不同的值分为以下几种类型：

其中 data cluster 以及 EOC marker 较为重要，通过它们可以构建一条 cluster chain，每个文件夹或文件的数据就存在于这样一条链上。

文件夹数据的 cluster chain 由若干 entry 组成，由于历史原因，为支持长文件名，entry 分为 LFN（long file name）以及 regular directory entry。常规 entry 只支持 8 位 ascii 文件名及 3 位 ascii 拓展名，想用使用长文件名需要在常规 entry 前接一条有 lfn entry 组成的 cluster chain。每个 lfn entry 除去序号，校验和，存储着最多 26 字节的 UCS-2（UTF-16 的一个子集）数据。而常规 entry 除了文件名，修改时间，创建时间，文件大小等元数据外，还存储着存放文件（夹）内容的第一个 cluster，读取文件（夹）内容需要读取该 cluster chain。

主要实现了一下三部份：

VFat 需要一个实现了 BlockDevice 的对象来初始化， BlockDevice 主要提供了 read_sector 和 write_sector 两个方法，用来读取 BlockDevice::sector_size() 字节的数据。最后把 SD card 驱动（该驱动是外部程序，CS140e 提供了一个名为 libsd.a 的文件，透过 FFI 调用）封装成一个 BlockDevice，用它初始化 VFat 即可操作 SD 卡上的 FAT32 文件系统。traits::FileSystem 要求的方法目前只实现了 open 的一部分。

traits::Dir 要求实现 fn entries(&self) -> io::Result<Self::Iter>;，即返回一个 Entry 的迭代器。读取 cluster chain 上的 entry 逐个返回即可。

trait::File 继承自 io::Read + io::Write + io::Seek 目前只实现了 io::Read，同样是读取对应的 cluster chain 填入 buffer 即可。

坑

最大的坑莫过于 CS140e 提供的测试数据有错，前后修改了三次测试数据才是正确的…… CS140e 的 e 其实是 experimental 的意思，我也该早就意识到做小白鼠是如此下场了 orz。

还有个坑是 FAT32 regular entry 的 ascii 是支持 256 字符的，而不是常见的，UTF-8 子集的 7 位 ascii，而 Rust 标准库并没有提供 256 字符 ascii 的处理函数，需要手动处理。起初没有发现的时候 parse utf8 偶尔会 panic。

jiegec 告诉我 MasterBootRecord 用了 #[repr(C, packed)] 导致 alignment 变成了 1，从而导致在 ARM 上读取 MasterBootRecord 里一个没对齐的 u32 会挂。不知为何，试了几次我的 MasterBootRecord 都是对齐的，等真的挂了再改成 align(4) 吧。

需要处理逻辑扇区和物理扇区之间的映射。起初我没有注意到，某次测试数据更新后在 read_cluster 中频频出现数组越界。 原因是其接受的 offset 参数可能大于一个物理扇区大小，得手动做些处理。由于所有读取 cluster 的操作都是通过这个函数实现的，改完就 OK 了。通过封装建立抽象屏障果然是灵丹妙药。

另外，从 Vec<T> cast 到 Vec<U> 并不能直接用 ::std::mem::transmute<T, U>(v)，原因是 Vec 除了数组数据以外，还有 len 和 cap 两个元数据，需要重新计算，即 Vec::from_raw_parts(new_ptr, new_len, new_cap)。同理，slice 含有len，也需要特别处理。不过 CS140e 提供了 VecExt::cast<T,U> 和 SliceExt::cast<T,U> 两个函数，印象中 nomicon 也提过这点，用错 transmute 也只能怪自己不小心（

Day 5

今天开始新的 assignment，3-spawn。主要是在写 AArch64 汇编。第一次写，肥肠痛苦。

今天写的这坨汇编做了什么？

当异常发生了，接下来发生什么？执行对应的异常向量里的指令：

整个 TrapFrame 有 800 字节（由于栈指针寄存器必须 16 字节对齐，有一个无意义的 32 位数据），其中 SIMD/FP 寄存器占了 512 字节。而且 AArch64 架构允许关闭这些寄存器，这时应该不保存这些寄存器到 TrapFrame。这一部分我暂时还没想好怎么实现比较合适。

不得不说 AArch64 汇编实在是紧凑过头了，人类 parse 起来很吃力。比如压栈，是这样写的：

    stp x0, x1, [SP, #-16]! // SP -= 16; *SP = x0, *(SP + 8) = x0

神他妈带副作用寻址模式，神他妈一次性 store 两个寄存器（stp = store pair）……

贵校的体系结构拆成三学期用三本书教，一堆概念重复三次，却每次都避开硬件异常不讲。我也一直偷懒没学，这次总算有了多少了解。

另外，这次提供的代码居然是编译不过的…… x30 存放着 link address，文档写着 lr 使它的别名。然而 CS140e 提供 aarch64-none-elf-gcc 的汇编器不认 lr。